1. Field of the Invention
The present invention relates to the field of error correction, as well as to the art of conducting parallel arithmetic operation for processing signals having symmetrical communication lines.
The present invention also is concerned with the art for executing various operations in coded recording of Reed-Solomon code, such as generation of syndrome, generation of GCD (greatest common divisor), error correction and erasure error correction.
More particularly, the invention is concerned with a method for executing the following computations: EQU y=r.sub.n-1 .multidot.x.sup.n-1 +r.sub.n-2 .multidot.x.sup.n-2 +. . . +r.sub.z .multidot.x+r.sub.0 ( 1) EQU y=GCD(A, B) (2)
where, GCD (A, B) represents the greatest common polynomial of polynomials A and B. EQU y=A.multidot.B (3)
where
A=a.sub.a .multidot.x.sup.n a.sub.n-1 .times.x.sup.n-1 +. . . +a.sub.1 .multidot.x+a.sub.0 B=b.sub.b .multidot.x.sup.n +b.sub.n-1 .multidot.x.sup.n'1 +. . . +b.sub.z .multidot.x+b.sub.0 EQU y=AmodB (4)
2. Related Background Art
In recent years, it is becoming popular to make use of error detect/ion/error correction codes (referred to simply as "error correction code" hereinafter) for the purpose of improving the reliability of various digital systems including memory systems.
Various error correction codes have been proposed for various systems, among which most popular is a class of linear codes generally referred to as "cyclic code". The cyclic code generally includes various codes such as BCH code suitable for random error correction, Fire code suitable for burst error correction, and Reed-Solomon code (referred to as "RS code" hereinafter) which is a kind of byte error correction and which is a kind of BCH code. Among these types of cyclic code, RS code is a significant one, because it can minimize the redundancy as compared with other linear codes having the same code length and error correction capacity. The RS code, therefore, has an increasing use in various fields of technology including satellite communication, magnetic disk and compact disk (referred to as "CD" hereinunder).
Various decoding methods for decoding RS code have been proposed. It is not too difficult to construct a decoder when the required correction capacity is as small as 2 to 3. For attaining a high reliability of the system, however, it is essential that the correction capacity is increased. The design for attaining a greater error correction capacity, however, is inevitably accompanied by problems such as an increase in the sale of correction apparatus, complication in the control of the apparatus, and longer computing time for decoding. To avoid such problems, in the field of CD, it has become a common measure to use a coding method known as CIRC which is a kind of dual coding method. This decoding method, however, is still unsatisfactory when used in systems which are required to have high operation speed and high reliability. In the field of opto-magnetic disk devices, it has been proposed to use a multiple error correction coding known as LDC (Long Distance Code), in order to obtain a high reliability. This code, however, does not make a contribution to the increase in the operation speed. Thus, it has been difficult to simultaneously handle the demands for high reliability and high speed which are essential in systems such as satellite communication systems.
On the other hand, current progress in semiconductor technology has made it possible to construct an RS code decoding apparatus in a VLSI scale. In the design of such apparatus, it is significant to adopt a coding method which makes efficient use of architectural features of VLSI, i.e., regular internal structure which affords a large scale of integration. The decoding process for RS code is composed of the following steps.
Step 1: Generation of syndrome.
Step 2: Generation of error position polynomial and error value polynomial.
Step 3: Generation of error position and error value.
Step 4: Execution of error correction.
Among these steps of RS code decoding process, Step 2 is the most complicated one. This step is conducted by using various algorithms such as Peterson's method, Berlekamp-Massey method, and Euclid mutual division (Euclidean algorithm). The formation of an error position polynomial and error value polynomial in accordance with the Euclidean algorithm can be regarded as a matter of expanded GCD (greatest common divisor) of the polynomials.
In general, questions concerning the expanded GCD can be solved by a systolic algorithm which is an algorithm developed by Kung et al and suitable for use in design of VLSI. The architecture of this algorithm is constituted by networks of simple processing elements (PE) and has the following features.
I) Arithmetic operations of networks of the same processor are conducted during transfer of data.
II) Networks between processors are formed by connecting adjacent processors in accordance with a predetermined rule.
III) A time delay of at least one unit is required for the transfer of data from a node (processor) to another node of the network.
This architecture is a system generally referred to as a pipeline system, and is capable of regularly circulating data so as to execute parallel arithmetic operation. In Addition, the error correcting capacity can be increased by increasing the number of PEs which operate in parallel.
A basic systolic algorithm for solving the expanded GCD of polynomials has been already proposed by Kung et al. This algorithm, however, has been derived on an assumption that it is executed by software by means of programmable systolic chip.